package ferp.core.ai.tree2;

import android.os.Debug;
import ferp.core.card.Card;
import ferp.core.game.Game;
import ferp.core.game.Trick;
import ferp.core.log.Log;
import ferp.core.player.Hand;

import java.util.LinkedHashSet;

/**
 * User: igorgok
 * Date: 1/8/12 12:41 PM
 */
public class Resolver
{
  // is resolver ready to serve requests
  public static boolean ready = false;

  public static synchronized void preallocate()
  {
    if (Node.pool.total() == 0)
    {
      Runtime r = Runtime.getRuntime();
      // do not use all the memory at once
      memory = r.maxMemory();
      // assume position/move ratio 1:7
      long nc = Math.round(Math.sqrt(memory)) * 6, mc = nc * 7;

      Log.debug(Log.TAG, "max memory: " + memory + ", preallocating " + nc + " nodes, " + mc + " moves");

      Node.pool.preallocate(nc);
      Move.pool.preallocate(mc);

      Log.debug(Log.TAG, "Resolver resources allocated successfully");
    }
    else
      Log.debug(Log.TAG, "Resolver resources already allocated");

    ready = true;
    Resolver.class.notify();
  }

  public static synchronized void initialize(int evaluator, int declarer, int starter, int trump, int hand0, int hand1, int hand2, byte talon0, byte talon1, int dropReal, int dropGuessed, int round, boolean open, boolean rostov)
  {
    while (!ready)
      try
      {
        Log.debug(Log.TAG, "resolver is not ready yet");
        Resolver.class.wait();
      }
      catch (InterruptedException e)
      {
        /* do nothing */
      }

    Resolver.recalculate = null;

    // initialize cancelled flag
    Resolver.cancelled = false;
    // store the evaluator
    Resolver.evaluator = Evaluator.evaluators[evaluator];
    // store the declarer
    Resolver.declarer = declarer;
    // store the starter
    Resolver.starter = starter;
    // store the trump
    Resolver.trump = Card.Suit.values()[trump];
    // store talon
    Resolver.talon[0] = talon0;
    Resolver.talon[1] = talon1;
    // store the drop
    Resolver.dropReal = dropReal;
    Resolver.dropGuessed = dropGuessed;
    // store open game flag
    Resolver.open = open;
    // store Rostov flag
    Resolver.rostov = rostov;
    // clear statistics
    Resolver.time = 0;
    Resolver.processed = Resolver.identical = 0;

    // clear previously created tree
    for (Level l : levels)
      l.clear(null);

    // create root position and add it at the depth 0 list
    Resolver.position = Node.create(levels[round], (byte)starter, hand0, hand1, hand2);
    Resolver.round = round;

    // set timeout according to the game type
    Resolver.timeout = declarer == Game.NO_ID ? PASSING_TIMEOUT : TRICKING_TIMEOUT;
  }

  public static synchronized void recalculateOnNextSolve(int hand0, int hand1, int hand2, int trick)
  {
    open = false;
    round = 0;
    time = 0;
    processed = identical = 0;

    recalculate = new Recalculate();

    recalculate.hand0 = hand0;
    recalculate.hand1 = hand1;
    recalculate.hand2 = hand2;
    recalculate.trick = trick;
  }

  // returns time in seconds spent on solving
  public static synchronized int solve()
  {
    if (recalculate != null)
    {
      Log.debug(Log.TAG, "resetting tree before solve for standing game");

      // clear previously created tree
      for (Level l : levels)
        l.clear(null);

      // create root position and add it at the depth 0 list
      Resolver.position = Node.create(levels[round], (byte)starter, recalculate.hand0, recalculate.hand1, recalculate.hand2);
    }

    // do nothing if there is no free memory
    refine();
    //  return 0;

    long start = System.currentTimeMillis();
    int highest = MAX_LEVEL;

    logSolveStart();

    //debug(true);

    // the main loop
    while (!cancelled && (Resolver.position.propagated & Score.COMPLETE) == 0 && Node.pool.in() > MIN_REQUIRED_NODES && Move.pool.in() > MIN_REQUIRED_MOVES)
    {
      for (int from = Resolver.round; from < MAX_LEVEL && Node.pool.in() > MIN_REQUIRED_NODES && Move.pool.in() > MIN_REQUIRED_MOVES && System.currentTimeMillis() - start < Resolver.timeout; /**/)
        for (Level current = levels[from]; current.round < MAX_LEVEL; current = levels[current.round + 1])
          if (current.pending.size() > 0)
            process(current);
          else
            // do not start from an empty level again
            if (from == current.round)
              ++from;

      // print out
      //for (Level current = levels[Resolver.depth]; current.depth < MAX_LEVEL; current = levels[current.depth + 1])
      //  logLevelInfo(current, status);

      logPoolState();

      // do we have to stop?
      boolean timeout = (System.currentTimeMillis() - start) > Resolver.timeout;
      // partially propagate score and store the highest level the score was propagated to
      highest = propagateScore(timeout);

      if (timeout)
        break;
    }

    // final score propagation if required
    //if (highest != round)
    //  propagateScore(true);

    long time = (System.currentTimeMillis() - start) / 1000;

    Resolver.time += time;

    logProcessingTime(time);
    logBestScore();

    if (recalculate != null && recalculate.trick != 0)
    {
      Log.debug(Log.TAG, "advancing after solve for standing game");

      advance(0, recalculate.trick);
    }

    recalculate = null;

    return (int)time;
  }

  // get the best move for the current position
  public static synchronized byte getBestMove(int depth, int hand, int trick, int cardsInHand)
  {
    final Card c0 = Trick.card(trick, 0);
    final Card c1 = Trick.card(trick, 1);

    Log.debug(Log.TAG, "getting best move for hand " + hand + ", depth " + depth + ", trick " + Trick.dump(trick, Card.Suit.NONE));

    // remove invalid moves
    for (position.children.start(); position.children.hasNextEntry(); /**/)
    {
      Move m = position.children.nextEntry();
      Card c = Card.card(m.card(hand));
      boolean invalid = (c.hash & cardsInHand) == 0;
      boolean mismatched = (c0 != null && (c0.compressed != m.c0 || (c1 != null && c1.compressed != m.c1)));

      if (invalid || mismatched)
      {
        // card is not in hand
        position.children.removeCurrentEntry();
        m.destroy();

        Log.debug(Log.TAG, invalid ? "removed invalid move " + c : "removed mismatched move " + m);
      }
    }

    // we may not guess the last card is in the real drop (human move)
    if (position.children.size() == 0)
      return Card.card(Hand.first(Hand.getMoveCandidates(cardsInHand, trick, trump))).compressed;

    // sort all available moves by score
    while (position.children.size() > 0)
    {
      Move m = getBestMove(hand, c0, c1);

      // move can be null if children have no scores
      if (m == null)
        m = position.children.first();

      //Log.debug(Log.TAG, "best #" + (index++) + ": " + Card.card(m.card(hand)) + ", " + Score.toString(Score.increment(m.node.propagated, m.node.winner)));

      position.children.remove(m);
      moves.addLast(m);
    }

    //debug(moves.size() == 0);

    seen.clear();
    // move sorted moves back to the position
    for (moves.start(); moves.hasNextEntry(); /**/)
    {
      Move m = moves.nextEntry();
      byte card = m.card(hand);

      moves.removeCurrentEntry();
      position.children.addLast(m);

      if (!seen.contains(card))
      {
        Log.debug(Log.TAG, "case #" + seen.size() + ": " + Card.card(card) + (depth == seen.size() || (depth > seen.size() && !moves.hasNextEntry()) ? "*" : "") + " " + Score.toString(m.node.propagated));
        seen.add(card);
      }
    }

    seen.toArray(sorted);

    return depth < seen.size() ? sorted[depth] : sorted[seen.size() - 1];
  }

  // best moves
  private static final LinkedList<Move> moves = new LinkedList<Move>(Move.class);
  private static final LinkedHashSet<Byte> seen = new LinkedHashSet<Byte>();
  private static final Byte[] sorted = new Byte[10];

  private static Move getBestMove(int hand, Card c0, Card c1)
  {
    final byte p0 = Resolver.position.player;
    final byte p1 = (byte)Game.next(p0);
    final byte p2 = (byte)Game.next(p1);

    short b0 = 0, b1 = 0, b2 = 0;
    Move result = null;

    LinkedList<Move> children = Resolver.position.children;

    children.start();

    switch (hand)
    {
      case 0: {
        for (Move current = children.nextEntry(), next = children.hasNextEntry() ? children.nextEntry() : null; current != null; current = next, next = children.hasNextEntry() ? children.nextEntry() : null)
        {
          Node child = current.node;

          if (child.propagated != 0)
          {
            short score = Score.increment(child.propagated, child.winner);

            if (b2 == 0 || evaluator.isBetter(score, b2, p2, declarer))
              b2 = score;
          }

          if (next != null && current.c0 == next.c0)
          {
            if (current.c1 != next.c1)
            {
              if (b2 != 0 && (b1 == 0 || evaluator.isBetter(b2, b1, p1, declarer)))
                b1 = b2;

              b2 = 0;
            }
          }
          else
          {
            if (b2 != 0 && (b1 == 0 || evaluator.isBetter(b2, b1, p1, declarer)))
              b1 = b2;

            if (b1 != 0 && (b0 == 0 || evaluator.isBetter(b1, b0, p0, declarer)))
            {
              b0 = b1;
              result = current;
            }

            b1 = b2 = 0;
          }
        }

        return result;
      }

      case 1: {
        // the condition (current.c0 == c0) should probably hold for all remaining children after advance()
        // removes all the others
        for (Move current = children.nextEntry(), next; current != null; current = next)
          if (current.c0 == c0.compressed)
          {
            Node child = current.node;

            for (next = null; children.hasNextEntry(); /**/)
            {
              Move m = children.nextEntry();

              if (m.c0 == c0.compressed)
              {
                next = m;
                break;
              }
            }

            short score = Score.increment(child.propagated, child.winner);

            if (b2 == 0 || evaluator.isBetter(score, b2, p2, declarer))
              b2 = score;

            if (next == null || current.c1 != next.c1)
            {
              if (b1 == 0 || evaluator.isBetter(b2, b1, p1, declarer))
              {
                b1 = b2;
                result = current;
              }

              b2 = 0;
            }
          }
          else
            next = children.hasNextEntry() ? children.nextEntry() : null;

        return result;
      }

      case 2: {
        while (children.hasNextEntry())
        {
          Move move = children.nextEntry();

          short score = Score.increment(move.node.propagated, move.node.winner);

          if (move.c0 == c0.compressed && move.c1 == c1.compressed && (b2 == 0 || evaluator.isBetter(score, b2, p2, declarer)))
          {
            b2 = score;
            result = move;
          }
        }

        return result;
      }
    }

    throw new AssertionError("invalid hand " + hand);
  }

/*
  private static byte verify(Move move, byte card, int hand, int trick, int cardsInHand)
  {
    Card c = Card.card(card);

    // check if the picked card is in the hand
    if ((cardsInHand & c.hash) != 0)
      return card;

    // card is not in the hand, it was dropped - delete this position
    position.children.remove(move);
    move.destroy();

    // and try to determine best move again (there must be more moves)
    if (position.children.size() > 0)
      return getBestMove(hand, trick, cardsInHand);

    Log.debug(Log.TAG, "all cards in drop, current cards in hand " + Hand.dump(cardsInHand) + ", returning " + Hand.dump(Hand.first(cardsInHand)));

    return Card.card(Hand.first(cardsInHand)).compressed;
  }
*/

  // get current best score for the current position
  public static synchronized short getBestScore()
  {
    return Resolver.position.propagated;
  }

  // go deeper to the next position as the game goes on removing unused ones
  public static synchronized void advance(int hand, int trick)
  {
    final Level current = levels[Resolver.round];
    final Card c0 = Trick.card(trick, 0);
    final int p1 = Game.next(Resolver.position.player);
    LinkedList<Move> children = Resolver.position.children;

    children.start();

    if (hand == 0)
    {
      boolean found = false;

      // look for move starting with c0
      while (children.hasNextEntry())
      {
        Move move = children.nextEntry();

        if (move.c0 == c0.compressed)
          found = true;
        else
        {
          children.removeCurrentEntry();
          move.destroy();
        }
      }

      if (!found)
      {
        // check the guessed drop
        checkGuessedDrop(c0, Resolver.position.player, trick);
        // no move found - create the (c0, x, y) branches
        process(current, Resolver.position, p1, trick, c0);
        // reset current propagated score (particularly, if it's complete next solve will not do anything)
        resetRootPosition(current);
      }

      return;
    }

    final Card c1 = Trick.card(trick, 1);
    final int p2 = Game.next(p1);

    if (hand == 1)
    {
      boolean found = false;

      // look for move starting with c0 and c1
      while (children.hasNextEntry())
      {
        Move move = children.nextEntry();

        if (move.c0 == c0.compressed && move.c1 == c1.compressed)
          found = true;
        else
        {
          children.removeCurrentEntry();
          move.destroy();
        }
      }

      if (!found)
      {
        // check the guessed drop
        checkGuessedDrop(c1, p1, trick);
        // no move found - create the (c0, c1, x) branches
        process(current, Resolver.position, p2, trick, c0, c1);
        // reset current propagated score (particularly, if it's complete next solve will not do anything)
        resetRootPosition(current);
      }

      return;
    }

    final Card c2 = Trick.card(trick, 2);
    Node child = null;

    // look for move with c0, c1 and c2
    while (children.hasNextEntry())
    {
      Move move = children.nextEntry();

      if (move.c0 == c0.compressed && move.c1 == c1.compressed && move.c2 == c2.compressed)
      {
        child = move.node;

        break;
      }
    }

    if (child == null)
    {
      // check the guessed drop
      checkGuessedDrop(c2, p2, trick);
      // no move found - create the (c0, c1, c2) branch
      // no need to reset root position here as it will be replaced with the "child"
      child = process(current, Resolver.position, trick, c0, c1, c2);
    }

    // the following should destroy the current position and decrease its children reference counters
    current.clear(null);
    // destroy all the nodes at the next level except the one we had found/created
    levels[Resolver.round + 1].clear(child);
    // this is the new tree root
    Resolver.position = child;
    // increase the depth
    ++Resolver.round;
  }

  private static void checkGuessedDrop(Card c, int player, int trick)
  {
    if ((c.hash & dropGuessed) != 0)
    {
      Log.debug(Log.TAG, "card played " + c + " is in guessed drop");

      Resolver.position.hands[player] = Hand.remove(Hand.add(Resolver.position.hands[player], dropGuessed), dropReal);
    }
    else
    {
      int candidates = Hand.getMoveCandidates(position.hands[player], Trick.remove(trick, Trick.size(trick) - 1), trump);

      if ((c.hash & candidates) == 0)
      {
        Log.debug(Log.TAG, "card played " + c + " is not in candidates " + Hand.dump(candidates));

        Resolver.position.hands[player] = Hand.remove(Hand.add(Resolver.position.hands[player], dropGuessed), dropReal);
      }
    }
  }

  private static void resetRootPosition(Level current)
  {
    // reset propagated score
    Resolver.position.propagated = 0;

    // move root back from "complete" to "processed" list if required
    switch (current.complete.size())
    {
      case 0:
        break;

      case 1:
        Node n = current.complete.removeFirst();

        if (n != Resolver.position)
          throw new AssertionError("some other node (not root) is in the list of complete nodes");

        current.processed.addLast(Resolver.position);

        break;

      default:
        throw new AssertionError("list of completed nodes contains " + current.complete.size() + " objects");
    }
  }

  // cancel solve execution
  public static void cancel() {Resolver.cancelled = true;}

  public static synchronized long getAvailableMemory() {return memory;}
  public static synchronized int getNodePoolCapacity() {return Node.pool.total();}
  public static synchronized int getMovePoolCapacity() {return Move.pool.total();}
  // get resolving speed
  public static synchronized int getSpeed() {return time > 0 ? Math.round(processed / time) : 0;}

  private static final int PASSING_TIMEOUT  = 1500; // 1.5 seconds
  private static final int TRICKING_TIMEOUT = 3000; // 3 seconds

  private static final int MIN_REQUIRED_NODES = 100;
  private static final int MIN_REQUIRED_MOVES = 100;

  // max number of rounds to calculate
  private static final int TOTAL_ROUNDS = 10;
  // max level index
  private static final int MAX_LEVEL = TOTAL_ROUNDS;
  // max tree depth
  private static final int TOTAL_LEVELS = MAX_LEVEL + 1;

  private static final class Recalculate
  {
    private int hand0;
    private int hand1;
    private int hand2;

    private int trick;
  }

  private static Recalculate recalculate;

  // available memory
  private static long memory;
  // tree levels
  private static final Level[] levels = new Level[TOTAL_LEVELS];
  // evaluator
  private static Evaluator evaluator;
  // game starter
  private static int starter;
  // game trump
  private static Card.Suit trump;
  // game declarer
  private static int declarer;
  // game talon
  private static byte[] talon = new byte[Game.TALON_SIZE];
  // cards dropped by declarer (real and guessed)
  private static int dropReal;
  private static int dropGuessed;
  // is game flavor Rostov ?
  private static boolean rostov;
  // is open game?
  private static boolean open;
  // current position
  private static Node position;
  // current depth
  private static int round;
  // hands
  private static int[] hands = new int[Game.PLAYERS];
  // cancelled flag
  private static boolean cancelled;
  // log buffer
  private static StringBuilder sb = new StringBuilder(512);

  // statistics
  private static long time;
  private static long processed;
  private static long identical;

  static {
      // initialize levels
      for (int i = 0; i < levels.length; ++i)
        levels[i] = new Level(i);
  }

  private static void process(Level current)
  {
    // remove first pending node and process it
    Node node = current.pending.removeFirst();
    int trick = trick(current.round);
    // get candidates for next move
    int candidates = evaluator.getMoveCandidates(node.hands, node.player, trick, trump, current.round, 0, declarer, dropReal, open);

    // create child positions
    for (int hash = evaluator.start(candidates); hash != 0; hash = evaluator.next(candidates, hash))
    {
      Card move = Card.card(hash);

      process(current, node, Game.next(node.player), Trick.add(trick, node.player, move.compressed), move);
    }

    // add to the processed list
    current.processed.addLast(node);
  }

  private static void process(Level current, Node parent, int nextPlayer, int trick, Card c0)
  {
    // get candidates for next move
    int candidates = evaluator.getMoveCandidates(parent.hands, nextPlayer, trick, trump, current.round, 1, declarer, dropReal, open);

    // create child positions
    for (int hash = evaluator.start(candidates); hash != 0; hash = evaluator.next(candidates, hash))
    {
      Card move = Card.card(hash);

      process(current, parent, Game.next(nextPlayer), Trick.add(trick, nextPlayer, move.compressed), c0, move);
    }
  }

  private static void process(Level current, Node parent, int nextPlayer, int trick, Card c0, Card c1)
  {
    // get candidates for next move
    int candidates = evaluator.getMoveCandidates(parent.hands, nextPlayer, trick, trump, current.round, 2, declarer, dropReal, open);

    // create child positions
    for (int hash = evaluator.start(candidates); hash != 0; hash = evaluator.next(candidates, hash))
    {
      Card move = Card.card(hash);

      process(current, parent, Trick.add(trick, nextPlayer, move.compressed), c0, c1, move);
    }
  }

  private static Node process(Level current, Node parent, int trick, Card c0, Card c1, Card c2)
  {
    // create new node
    Node node;
    Level deeper = levels[current.round + 1];
    byte winner = Trick.winner(trick, trump);
    boolean map = declarer != Game.NO_ID || current.round >= Game.TALON_SIZE || rostov;

    int p0 = parent.player;
    int p1 = Game.next(p0);
    int p2 = Game.next(p1);

    // remove played cards from hands
    hands[p0] = Hand.remove(parent.hands[p0], c0.hash);
    hands[p1] = Hand.remove(parent.hands[p1], c1.hash);
    hands[p2] = Hand.remove(parent.hands[p2], c2.hash);

    // do not look for duplicate sub-trees in initial passing rounds as there might be multiple winners
    if (map)
    {
      if ((node = Node.set.get(Node.key(winner, hands))) == null)
      {
        // position not found - create new one
        node = Node.create(deeper, parent, hands, winner, winner, c0, c1, c2);
        // store this position in the hash map
        Node.set.put(node);
      }
      else
      {
        // add existing node as a child and increment its number of parents
        parent.children.addLast(Move.create(c0, c1, c2, node));

        ++node.parents;
        ++Resolver.identical;
      }
    }
    else
      // set the correct starting player for the next round
      node = Node.create(deeper, parent, hands, (byte)starter, winner, c0, c1, c2);

    // collect processed nodes statistics
    ++Resolver.processed;

    return node;
  }

  private static int trick(int round)
  {
    // if passing game open a talon card before first hand plays
    return declarer == Game.NO_ID && !Resolver.rostov && round < Game.TALON_SIZE ? Trick.add(0, talon[round]) : 0;
  }

  // propagate score and perform pruning
  // return highest level where score was propagated
  private static int propagateScore(boolean finaL)
  {
    //debug(true);

    // initialize score at the bottom (all the nodes are in the "pending" list)
    for (levels[MAX_LEVEL].pending.start(); levels[MAX_LEVEL].pending.hasNextEntry();)
    {
      Node node = levels[MAX_LEVEL].pending.nextEntry();

      node.propagated = Score.COMPLETE;
    }

    // maxN algorithm - propagate score upwards starting from the level before last
    int d = MAX_LEVEL - 1;

    for (; d >= Resolver.round; d--)
    {
      //debug(d == 2);
      for (levels[d].processed.start(); levels[d].processed.hasNextEntry(); /**/)
      {
        Node node = levels[d].processed.nextEntry();

        if (node.children.size() > 0)
        {
          byte p0 = node.player;
          byte p1 = (byte)Game.next(p0);
          byte p2 = (byte)Game.next(p1);
          short b0 = 0, b1 = 0, b2 = 0, complete = Score.COMPLETE;
          LinkedList<Move> children = node.children;

          children.start();

          for (Move current = children.nextEntry(), next = children.hasNextEntry() ? children.nextEntry() : null; current != null; current = next, next = children.hasNextEntry() ? children.nextEntry() : null)
          {
            Node child = current.node;
            short score = 0;

            // update completeness flag - eventually will be set only if all the child scores are complete
            complete = (short)(complete & child.propagated);

            if (child.propagated != 0)
            {
              score = Score.increment(child.propagated, child.winner);

              if (b2 == 0 || evaluator.isBetter(score, b2, p2, declarer))
                b2 = score;
            }

            if (next != null && current.c0 == next.c0)
            {
              if (current.c1 != next.c1)
              {
                if (b2 != 0 && (b1 == 0 || evaluator.isBetter(b2, b1, p1, declarer)))
                  b1 = b2;

                b2 = 0;
              }
            }
            else
            {
              if (b2 != 0 && (b1 == 0 || evaluator.isBetter(b2, b1, p1, declarer)))
                b1 = b2;

              if (b1 != 0 && (b0 == 0 || evaluator.isBetter(b1, b0, p0, declarer)))
                b0 = b1;

              b1 = b2 = 0;
            }
          }

          // set the new best score considering computed completeness bit
          node.propagated = (short)(((b0 == 0 ? (b1 == 0 ? b2 : b1) : b0) & Score.SCORE) | complete);

          // prune weak moves only if the sub-tree is complete
          if (complete != 0)
          {
            // move this node to the "complete" list
            levels[d].processed.removeCurrentEntry();

            levels[d].complete.addLast(node);
            // we will refine the tree from the level next to this one
            //from = d;
          }
  /*
            for (Iterator<Move> mi = node.children.iterator(); mi.hasNext();)
            {
              Node child = mi.next().node;

              if (child != chosen)
              {
                // remove the node from child list
                mi.remove();
                // and dereference it, so the removeUnusedPosition will collect it
                if (--child.parents < 1)
                  ++pruned;
              }
            }
          }
  */
        }
      }
    }

/*
    if (pruned > 0)
    {
      logPruningResult(pruned);
      // remove pruned nodes
      if (!finaL)
        refine(from + 1);
    }
*/

    return d + 1;
  }

  private static int refine() {return refine(Resolver.round + 1);}
  private static int refine(int from)
  {
    int removed = 0;

    // walk down the tree
    for (int d = from; d < TOTAL_LEVELS; ++d)
    {
      Level level = levels[d];

      // now remove the unused nodes in both lists
      removed += refine(level.complete) + refine(level.processed) + refine(level.pending);
      //removed += refine(level.processed) + refine(level.pending);

      // clear scores in the list of processed nodes
      //for (Node n : level.processed)
      //  n.propagated = 0;
    }

    logRefineResult(removed, from);

    return removed;
  }

  private static int refine(LinkedList<Node> list)
  {
    int size = list.size();

    // now remove the unused nodes
    for (list.start(); list.hasNextEntry();)
    {
      Node n = list.nextEntry();

      if (n.parents == 0)
      {
        list.removeCurrentEntry();
        n.destroy();
      }
    }

    // how many nodes were removed
    return size - list.size();
  }

  private static void logSolveStart()
  {
    sb.setLength(0);

    sb.append("building tree from depth ").append(Resolver.round);

    Log.debug(Log.TAG, sb.toString());
  }

/*
  private static void logLevelInfo(Level level, Status status)
  {
    sb.setLength(0);

//    sb.append('@').append(depth).append(" - positions: processed=").append(level.processed.size()).append(", pending=")
//      .append(level.pending.size()).append(", added=").append(status.added).append(", identical=").append(status.identical);

    sb.append('@').append(level.depth).append(" - (").append(status.processed).append(',').append(status.pending1).append("), processed=")
      .append(level.processed.size() - status.processed).append(", added=").append(status.added).append(", identical=").append(status.identical);

    Log.d(TAG, sb.toString());
  }
*/

  private static void logProcessingTime(long time)
  {
    sb.setLength(0);

    sb.append("processing time ").append(time).append('s').append(", processed ").append(processed).append(", identical ").append(identical);

    Log.debug(Log.TAG, sb.toString());
  }

  private static void logPoolState()
  {
    sb.setLength(0);

    sb.append("pools state: node (").append(Node.pool.total()).append(',').append(Node.pool.in()).append("), move (")
      .append(Move.pool.total()).append(',').append(Move.pool.in()).append(')');

    Log.debug(Log.TAG, sb.toString());
  }

  private static void logBestScore()
  {
    sb.setLength(0);

    sb.append("best score for player ").append(Resolver.position.player).append(": ").append(Score.toString(Resolver.position.propagated));

    Log.debug(Log.TAG, sb.toString());
  }

  private static void logValue(String message, int value)
  {
    sb.setLength(0);

    sb.append(message).append(value);

    Log.debug(Log.TAG, sb.toString());
  }

  private static void logPruningResult(int pruned)
  {
    logValue("nodes pruned ", pruned);
  }

  private static void logRefineResult(int removed, int from)
  {
    sb.setLength(0);

    sb.append("nodes removed ").append(removed).append(" from level ").append(from);

    Log.debug(Log.TAG, sb.toString());

    logPoolState();
  }

  public static void debug(boolean when)
  {
    //if (!Config.PRODUCTION && when)
    if (when)
    {
      Log.debug(Log.TAG, "waiting for debugger...");
      Debug.waitForDebugger();
    }
  }

  private static int timeout;

  // resolver test
/*
  public static void main(String[] args) throws Exception
  {
    TestLog log = new TestLog();
    Deck deck = Deck.instance();
    int[] hands = new int[Game.PLAYERS];
    ArrayList<Integer> counts = new ArrayList<Integer>(Game.PLAYERS);
    ArrayList<Card> talon = new ArrayList<Card>(Game.TALON_SIZE);
    ArrayList<Card> cards = new ArrayList<Card>(12);
    double ratio = Double.MIN_VALUE;

    Resolver.preallocate();

    for (int i = 0; i < Game.PLAYERS; ++i)
      counts.add(0);

    for (int g = 0; true; ++g)
    {
      log.open();

      int gameType = random.nextInt(Evaluator.TRICKING + 1);
      int starter = random.nextInt(Game.PLAYERS);
      // simulate human play
      int declarer = gameType == Evaluator.PASSING ? Game.NO_ID : 0;
      //int declarer = gameType == Evaluator.PASSING ? Game.NO_ID : random.nextInt(Game.PLAYERS);
      Card.Suit trump = gameType == Evaluator.TRICKING ? Card.Suit.values()[random.nextInt(Card.Suit.values().length)] : Card.Suit.NONE;
      int drop = 0;

      talon.clear();
      cards.clear();
      deck.shuffle();

      // deal
      for (int i = 0, h = 0; i < Deck.SIZE - Game.TALON_SIZE; h = (h + 1) % Game.PLAYERS)
        for (int n = 0; n < 2; ++n, ++i)
        {
          Card c = deck.card(i);

          hands[h] = Hand.add(hands[h], c.hash);

          if (h == declarer)
            cards.add(c);
        }

      // remaining cards go to the talon
      for (int i = 0; i < Game.TALON_SIZE; ++i)
        talon.add(deck.card(Deck.SIZE - Game.TALON_SIZE + i));

      if (gameType != Evaluator.PASSING)
      {
        cards.addAll(talon);
        hands[declarer] = Hand.add(hands[declarer], talon.get(0).hash | talon.get(1).hash);

        for (int i = 0; i < Game.TALON_SIZE; ++i)
        {
          int index = random.nextInt(cards.size());
          Card c = cards.remove(index);

          hands[declarer] = Hand.remove(hands[declarer], c.hash);
          drop = Hand.add(drop, c.hash);
        }
      }

*/
/*
      gameType = 0;
      declarer = 0; starter = 2; trump = Card.Suit.NONE;
      hands[0] = 171216922; hands[1] = 80299077; hands[2] = -251524320;
      talon.add(Card.card((byte)21)); talon.add(Card.card((byte)22));
      drop = 8320;
      int[] tricks = {-1063189913,-1073200762,-1070370425,-1063123864,-1073396829,-1072148078,-1070042476,-1070107499,-1070172777};
      //hands[declarer] = Hand.remove(Hand.add(hands[declarer], talon.get(0).hash | talon.get(1).hash), drop);
*//*


      System.out.println("Starting game #" + g + ", type " + gameType + ", declarer " + declarer + ", starter " + starter + ", trump " + trump);
      System.out.println("hands: [" + hands[0] + "], [" + hands[1] + "], [" + hands[2] + "]");
      System.out.println("hands: [" + Hand.dump(hands[0]) + "], [" + Hand.dump(hands[1]) + "], [" + Hand.dump(hands[2]) + "]");
      System.out.println("talon: " + talon.get(0).toString() + ' ' + talon.get(1).toString() + " (" + talon.get(0).compressed + ", " + talon.get(1).compressed + ")");
      System.out.println("drop: " + Hand.dump(drop) + " (" + drop + ")");

      int h0 = hands[0];

      if (declarer == 0)
      {
        h0 = gameType == Evaluator.MISERE ? Guess.declarerMisereHand(h0 | drop, drop) : Guess.declarerTrickingHand(h0 | drop, starter == declarer, g);

        System.out.println("guessed hand [" + Hand.dump(h0) + "], drop: " + Hand.dump((hands[0] | drop) & ~h0));
      }

      Resolver.initialize(gameType, declarer, starter, trump.ordinal(), h0, hands[1], hands[2], talon.get(0).compressed, talon.get(1).compressed, drop, (hands[0] | drop) & ~h0, 0, true, false);

      Collections.fill(counts, 0);

      for (int r = 0; r < 10; ++r)
      {
        int trick = trick(r);
        byte player = Resolver.position.player;

        solve();

        // update ratio
        ratio = Math.max((double)Move.pool.out() / Node.pool.out(), ratio);

        for (int h = 0; h < Game.PLAYERS; ++h)
        {
          // always return best move for testing purposes
          getBestMove(10, h, trick, hands[player]);

          Card c = Card.card(player > 0 ? getBestMove(0, h, trick, hands[player]) : getRandomMove(hands, player, trick, trump, r, h, declarer, drop));
          //Card c = Card.restore(player > 0 ? getBestMove(h, trick, hands[player]) : getHumanMove(h, trick, hands[player], tricks));
          //Card c = Card.restore(getRecordedMove(tricks, round, h, player, trick, hands[player]));

          // put card to trick
          trick = Trick.add(trick, player, c.compressed);
          // advance resolver
          advance(h, trick);
          // remove played card from hand
          hands[player] = Hand.remove(hands[player], c.hash);

          player = (byte)Game.next(player);
        }

        System.out.println("#" + r + ":" + Trick.dump(trick, trump));

        byte winner = Trick.winner(trick, trump);
        counts.set(winner, counts.get(winner) + 1);
      }

      System.out.println("--- " + counts + " ----------------------------------------------------------------[" + ratio + ']');

      log.close();
    }
  }

  private static byte getRandomMove(int[] hands, int player, int trick, Card.Suit trump, int round, int hand, int declarer, int drop)
  {
    int candidates = evaluator.getMoveCandidates(hands, player, trick, trump, round, hand, declarer, drop, true);
    int first = evaluator.start(candidates);
    int size = 0;
    Card card = null;

    for (int hash = first; hash != 0; hash = evaluator.next(candidates, hash))
      ++size;

    for (int hash = first, n = random.nextInt(size); n >= 0; hash = evaluator.next(candidates, hash), --n)
      card = Card.card(hash);

    return card.compressed;
  }

  private static byte getHumanMove(int hand, int trick, int cardsInHand, int[] tricks)
  {
    Scanner scanner = new Scanner(System.in);

    System.out.println("moves: " + Trick.dump(trick, trump));
    System.out.println("cards in hand " + Hand.dump(cardsInHand));

    if (tricks.length > round)
      System.out.println("hint " + Trick.dump(tricks[round], trump));

    System.out.print("enter suit 0-3: ");
    Card.Suit s = Card.Suit.values()[scanner.nextInt()];

    System.out.print("\nenter rank 7-14: ");
    Card.Rank r = Card.Rank.values()[scanner.nextInt() - 7];

    return Card.card(s, r).compressed;
  }

  private static byte getRecordedMove(int[] tricks, int round, int hand, int player, int trick, int cardsInHand)
  {
    System.out.println("cards in hand " + Hand.dump(cardsInHand));

    if (tricks.length > round)
    {
      System.out.println("hint " + Trick.dump(tricks[round], trump));

      Card c = Trick.card(tricks[round], hand);

      if (c != null)
        return c.compressed;
    }

    System.out.println("no more recorded moves");

    //return player > 0 ? getBestMove(hand, trick, cardsInHand) : getHumanMove(hand, trick, cardsInHand, tricks);
    return getBestMove(0, hand, trick, cardsInHand);
  }

  private static class TestLog extends Log
  {
    public TestLog() throws Exception
    {
      parent = new File("D:\\Long run test");
      if (!parent.exists() && !parent.mkdir())
        throw new Exception("Failed to create log directory " + parent.getName());

      file = File.createTempFile("log", ".txt", parent);

      log = this;
    }

    @Override
    protected void d(String tag, String msg)
    {
      System.out.println(msg);

      try
      {
        if (msg.startsWith("working cells"))
          fos.write((msg + "\n").getBytes());
      }
      catch (IOException e)
      {
        e.printStackTrace();
      }
    }

    @Override
    protected void e(String tag, Throwable t)
    {
      close();

      t.printStackTrace();
      System.exit(-1);
    }

    public void open() throws Exception
    {
      fos = new FileOutputStream(file, true);
    }

    public void close()
    {
      try
      {
        fos.close();
      }
      catch (IOException e)
      {
        e.printStackTrace();
      }
    }

    private File parent;
    private File file;
    private FileOutputStream fos;
  }

  private static final Random random = new Random();
*/
}
